package solution;

import common.TreeNode;

import java.util.*;

/**
 * @author zhangmin
 * @create 2021-08-10 10:56
 */
public class Solution_6DP {

    /*===========================================================================================================================
     *DP 509. 斐波那契数
     * 斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
     * 1.备忘录的递归
     *  */

    public int fib(int n) {
        int[] memo=new int[n+1];
        return dp(memo,n);
    }
    private int dp(int[] memo,int n){
        if(n==1||n==0)return n;
        if (memo[n]!=0) return memo[n];
        memo[n]=dp(memo,n-1)+dp(memo,n-2);
        return memo[n];
    }
    /*
     * 2.dp的迭代解法
     * f(n)=f(n-1)+f(n-2),n>2
     * f(n)=1,n=1,2
     *  */
    public int fib1(int n) {
        if (n==0)return 0;
        int[] f=new int[n+1];
        f[0]=0;f[1]=1;
        for (int i = 2; i <=n ; i++) {
            f[i]=f[i-1]+f[i-2];
        }
        return f[n];
    }
    public int fib2(int n) {
        if (n==0)return 0;
        if (n==1||n==2) return 1;
        //状态压缩
        int p=1,c=1;
        for (int i = 3; i <=n ; i++) {
            int s=p+c;
            p=c;
            c=s;
        }
        return c;
    }

    /*===========================================================================================================================
     *DP 322. 零钱兑换
     * 整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数
     *  */
    //暴力求解:dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。
    public int coinChange1(int[] coins, int amount) {
        return dp1(coins,amount);
    }
    private int dp1(int[] coins,int amount){
        if (amount==0) return 0;
        if (amount<0) return -1;
        int  res=Integer.MAX_VALUE;
        for (int coin:coins) {
            int subPro=dp1(coins,amount-coin);
            if (subPro==-1)continue;
            // 在子问题中选择最优解，然后加一
            res=Math.min(res,subPro+1);
        }
        return res==Integer.MAX_VALUE?-1:res;
    }
    //带备忘录的递归
    int[] memo;
    public int coinChange2(int[] coins, int amount) {
        memo=new int[amount+1];
        Arrays.fill(memo,-1);
        return dp2(coins,amount);
    }
    private int dp2(int[] coins,int amount){
        if (amount==0) return 0;
        if (amount<0) return -1;
        if (memo[amount]!=-1)
            return memo[amount];
        int  res=Integer.MAX_VALUE;
        for (int coin:coins) {
            int subPro=dp2(coins,amount-coin);
            if (subPro==-1)continue;
            // 在子问题中选择最优解，然后加一
            res=Math.min(res,subPro+1);
        }
        memo[amount]=(res==Integer.MAX_VALUE?-1:res);
        return memo[amount];
    }

    //dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。
    // dp(n)=min{dp(n-coin)+1|coin属于coins}，n>0
    //dp(0)=0,dp(n)=-1,n<0
    public int coinChange(int[] coins, int amount) {
        // 数组大小为 amount + 1，初始值也为 amount + 1
        int[] dp=new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0]=0;
        for (int i = 1; i <=amount ; i++) {
            for (int coin:coins) {
                if (i-coin<0) continue;
                dp[i]=Math.min(dp[i],1+dp[i-coin]);
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];
    }


    /*===========================================================================================================================
     *DP 931. 下降路径最小和
     *  */
    //递归+备忘录：dp 函数的含义如下：从第一行（matrix[0][..]）向下落，落到位置 matrix[i][j] 的最小路径和为 dp(matrix, i, j)。
    // 知道到达 (i-1, j), (i-1, j-1), (i-1, j+1) 这三个位置的最小路径和，加上 matrix[i][j] 的值，就能够计算出来到达位置 (i, j) 的最小路径和
    // 备忘录
    int[][] memo931;
    private int dp931(int[][] matrix,int i,int j){
        if (i<0||j<0||i>=matrix.length||j>=matrix[0].length)
            // 返回一个特殊值:合法答案的区间是 [-10000, 10000]，所以我们的返回值只要大于 10000 就相当于一个永不会取到的最大值。
            return 99999;
        if (i==0){
            //base case:第一行数据
            return matrix[0][j];
        }
        if (memo931[i][j]!=66666)return memo931[i][j];
        memo931[i][j]=matrix[i][j]+Math.min(dp931(matrix,i-1,j),Math.min(dp931(matrix,i-1,j-1),dp931(matrix,i-1,j+1)));
        return memo931[i][j];
    }
    public int minFallingPathSum(int[][] matrix) {
        int n=matrix.length;
        int res=Integer.MAX_VALUE;
        memo931=new int[n][n];
        for (int i = 0; i < n; i++) {
            //matrix 是 n x n 的二维数组，其中 1 <= n <= 100；对于二维数组中的元素，有 -100 <= matrix[i][j] <= 100。得到的路径和就是 100 x 100 = 10000，也就是最大的合法答案。这个问题的合法结果会落在区间 [-10000, 10000] 中
            //所以，我们 memo 的初始值就要避开区间 [-10000, 10000]
            Arrays.fill(memo931[i],66666);
        }
        for (int i = 0; i < n; i++) {
            res=Math.min(res,dp931(matrix,n-1,i));
        }
        return res;
    }

    /*===========================================================================================================================
     *DP 64. 最小路径和
     * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或者向右移动一步。
     *  */
    //递归+备忘录
    int[][] memo64;
    //dp表示从左上角位置 (0, 0) 走到位置 (i, j) 的最小路径和为 dp(grid, i, j)。
    int dp64(int[][] grid,int i,int j){
        if (i==0&&j==0) return grid[0][0];
        if (i<0||j<0){
            return Integer.MAX_VALUE;
        }
        if (memo64[i][j]!=-1){
            return memo64[i][j];
        }
        memo64[i][j]=Math.min(dp64(grid,i-1,j),dp64(grid,i,j-1))+grid[i][j];
        return memo64[i][j];
    }
    public int minPathSum1(int[][] grid) {
        int n=grid.length;
        int m=grid[0].length;
        memo64=new int[n][m];
        for (int[] row:memo64) {
            Arrays.fill(row,-1);
        }
        return dp64(grid,n-1,m-1);
    }
    //自底向上dp
    public int minPathSum(int[][] grid) {
        int n=grid.length;
        int m=grid[0].length;
        int[][] dp=new int[n][m];
        //base case
        dp[0][0]=grid[0][0];
        for (int i = 1; i <n ; i++) {
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for (int i = 1; i < m; i++) {
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[n-1][m-1];
    }


    /*===========================================================================================================================
     *DP 174. 地下城游戏
     * 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
     * 输入一个存储着整数的二维数组 grid，如果 grid[i][j] > 0，说明这个格子装着血瓶，经过它可以增加对应的生命值；
     * 如果 grid[i][j] == 0，则这是一个空格子，经过它不会发生任何事情；如果 grid[i][j] < 0，说明这个格子有怪物，经过它会损失对应的生命值。
     * 你只能向右和向下移动，请问你初始至少需要多少生命值才能成功救出公主？
     *  */
    //关键不在于吃最多的血瓶，而是在于如何损失最少的生命值。
    public int calculateMinimumHP(int[][] dungeon) {
        int n=dungeon.length;
        int m=dungeon[0].length;
        //从 grid[i][j] 到达终点（右下角）所需的最少生命值是 dp(i, j)=min(dp(i + 1, j),dp(i, j + 1)) - dungeon[i][j];
        int[][] dp=new int[n][m];
        dp[n-1][m-1]=dungeon[n-1][m-1]>=0? 1:-dungeon[n-1][m-1]+1;
        for (int i = m-2; i >= 0 ; i--) {
            int t1=dp[n-1][i+1]-dungeon[n-1][i];
            dp[n-1][i]=t1<=0? 1:t1;
        }
        for (int i = n-2; i >=0; i--) {
            int t2=dp[i+1][m-1]-dungeon[i][m-1];
            dp[i][m-1]=t2<=0?1:t2;
        }
        for (int i = n-2; i >=0 ; i--) {
            for (int j = m-2; j >=0 ; j--) {
                int t=Math.min(dp[i][j+1],dp[i+1][j])-dungeon[i][j];
                dp[i][j]=t<=0? 1:t;
            }
        }
        return dp[0][0];
    }


    /*===========================================================================================================================
     *DP 514. 自由之路
     * 给定一个字符串 ring，表示刻在外环上的编码；给定另一个字符串 key，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。
     * 将 ring 顺时针或逆时针旋转一个位置，计为1步。如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。
     * 「状态」就是「当前需要输入的字符」和「当前圆盘指针的位置」。dp(i,j)的定义如下：
     * 当圆盘指针指向 ring[i] 时，输入字符串 key[j..] 至少需要 dp(ring, i, key, j) 次操作。
     *  */
    int[][] memo514;
    int dp514(String ring,int i,String key,int j){
        //base case 完成输入
        if (j==key.length()) return 0;
        if (memo514[i][j]!=0){
            return memo514[i][j];
        }
        int n=ring.length();
        int res=Integer.MAX_VALUE;
        for (int k = 0; k < ring.length(); k++) {
            //ring上可能的key[j]都进行考虑
            if (ring.charAt(k)==key.charAt(j)){
                //count记录拨动指针的次数，可能顺时针，可能逆时针
                int count=Math.abs(k-i);
                count=Math.min(count,n-count);
                //递归，ring指向k，找key[j+1]
                int subRes=dp514(ring,k,key,j+1);
                //按按钮也是一次操作
                res=Math.min(res,count+subRes+1);
            }
        }
        memo514[i][j]=res;
        return res;
    }
    public int findRotateSteps(String ring, String key) {
        int rl=ring.length();
        int kl=key.length();
        memo514=new int[rl][kl];
        for (int[] row:memo514) {
            Arrays.fill(row,0);
        }
        return dp514(ring,0,key,0);
    }

    /*===========================================================================================================================
     *DP 787. K 站中转内最便宜的航班
     * 正整数 n 代表城市个数，数组 flights 装着若干三元组代表城市间的航线及价格，城市编号 src 代表你所在的城市，城市编号 dst 代表你要去的目标城市，整数 K 代表你最多经过的中转站个数。
     * 计算，在 K 次中转之内，从 src 到 dst 所需的最小花费是多少钱，如果无法到达，则返回 -1。
     * 很明显，这题就是个加权有向图中求最短路径的问题。同时要满足，这条路径最多不能超过 K + 1 条边
     *  */
    /* 定义：从起点 src 出发，k 步之内（一步就是一条边）到达节点 s 的最小路径权重为 dp(s, k)。
    dp(dst, k) = min(dp(s1, k - 1) + w1, dp(s2, k - 1) + w2)
    */
    //用来存储每个点的入度
    Map<Integer, List<int[]>> indegree;
    int src787,dst787;
    int[][] memo787;
    int dp787(int s,int k){
        if (s==src787){
            return 0;
        }
        if (k==0){
            return -1;
        }
        if (memo787[s][k]!=-999){
            return memo787[s][k];
        }
        int res=Integer.MAX_VALUE;
        if (indegree.containsKey(s)){
            for (int[] v:indegree.get(s)) {
                int from=v[0];
                int price=v[1];
                int subRes=dp787(from,k-1);
                if (subRes!=-1){
                    res=Math.min(res,subRes+price);
                }
            }
        }
        memo787[s][k]=res==Integer.MAX_VALUE?-1:res;
        return  memo787[s][k];
    }
    public int findCheapestPrice1(int n, int[][] flights, int src, int dst, int k) {
        src787=src;
        dst787=dst;
        indegree=new HashMap<>();
        for (int[] f:flights) {
            indegree.putIfAbsent(f[1],new LinkedList());
            indegree.get(f[1]).add(new int[]{f[0],f[2]});
        }
        memo787=new int[n][k+2];
        for (int[] row:memo787) {
            Arrays.fill(row,-999);
        }
        return dp787(dst,k+1);
    }
    /*自底向上：f[t][i] 表示通过恰好 t 次航班，从出发城市 src 到达城市 i 需要的最小花费.*/
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        final int INF=10000*101+1;
        int[][] dp=new int[k+2][n];
        for (int i = 0; i < k+2; i++) {
            Arrays.fill(dp[i],INF);
        }
        dp[0][src]=0;
        for (int t = 1; t < k+2; t++) {
            for (int[] flight:flights) {
                int j=flight[0],i=flight[1],pr=flight[2];
                dp[t][i]=Math.min(dp[t][i],dp[t-1][j]+pr);
            }
        }
        int res=INF;
        for (int t = 1; t < k+2; t++) {
            res=Math.min(res,dp[t][dst]);
        }
        return res==INF?-1:res;
    }


    /*===========================================================================================================================
     *DP 10. 正则表达式匹配
     * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
     * '.' 匹配任意单个字符，'*' 匹配零个或多个前面的那一个元素
     *  */
    Map<String,Boolean> memo10;
    //「状态」无非就是i和j两个指针的位置，「选择」就是p[j]选择匹配几个字符。
    //dp(s,i,p,j)函数的定义:s[i..]是否可以匹配p[j..]
    boolean dp10(String s,int i,String p,int j){
        //base case
        //这意味着模式串p已经被匹配完了，那么应该看看文本串s匹配到哪里了，如果s也恰好被匹配完，则说明匹配成功
        if (j==p.length()) return i==s.length();
        //i到s的最后时，并不能根据j是否等于p.size()来判断是否完成匹配，只要p[j..]能够匹配空串，就可以算完成匹配。
        if (i==s.length()){
            if ((p.length()-j)%2==1){
                // 如果能匹配空串，一定是字符和 * 成对儿出现
                return false;
            }
            for (;j+1<p.length();j+=2){
                if (p.charAt(j+1)!='*'){
                    return false;
                }
            }
            return true;
        }
        String key=i+","+j;
        if (memo10.containsKey(key)) return memo10.get(key);

        boolean res=false;
        if (s.charAt(i)==p.charAt(j)||p.charAt(j)=='.'){
            //ij匹配
            if (j<p.length()-1&&p.charAt(j+1)=='*'){
                //p下一个是*，需要选择时匹配0次（直接越过当前的j和后面的*，s[i]去匹配p[j+2]）还是多次(用p[j]接着去匹配s[i+1])
                res= dp10(s,i,p,j+2)||dp10(s,i+1,p,j);
            }else {
                //常规匹配一次
                res= dp10(s,i+1,p,j+1);
            }
        }else {
            //i，j不匹配
            if (j<p.length()-1&&p.charAt(j+1)=='*'){
                //*匹配0次
                res= dp10(s,i,p,j+2);
            }else {
                //无法继续匹配
                res= false;
            }
        }
        memo10.put(key,res);
        return res;

    }
    public boolean isMatch(String s, String p) {
        memo10=new HashMap<>();
        return dp10(s,0,p,0);
    }




    /*===========================================================================================================================
     *DP 887. 鸡蛋掉落
     * 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
     * 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。
     * 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
     * 关键：有很多种方法获得这个f但是需要求的是这些方法种操作次数最小的方法会操作多少次
     *  */
    //方法1：常规dp
    Map<String,Integer> memo887;
    //当前状态为 (K 个鸡蛋，N 层楼),返回这个状态下的最优结果(最少操作次数)
    int dp887_1(int k,int n){
        //base case 当楼层数N等于 0 时，显然不需要扔鸡蛋；当鸡蛋数K为 1 时，显然只能线性扫描所有楼层
        if (k==1) return n;
        if (n==0) return 0;
        String key=k+"="+n;
        if (memo887.containsKey(key)){
            return memo887.get(key);
        }
        int res=Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            res=Math.min(res,Math.max(dp887(k,n-i),dp887(k-1,i-1))+1);
        }
        memo887.put(key,res);
        return res;
    }
    public int superEggDrop1(int k, int n) {
        memo887=new HashMap<>();
        return dp887(k,n);
    }

    /*方法2：二分查找优化：
    * 根据dp(K, N)数组的定义（有K个鸡蛋面对N层楼，最少需要扔 dp(K, N) 次），很容易知道K固定时，这个函数随着N的增加一定是单调递增的，
    * 无论你策略多聪明，楼层增加的话，测试次数一定要增加。
    * dp(K - 1, i - 1)和dp(K, N - i)这两个函数，如果我们固定K和N，把这两个函数看做关于i的函数，前者随着i的增加应该也是单调递增的，而后者随着i的增加应该是单调递减的
    * */
    int dp887(int k,int n){
        //base case 当楼层数N等于 0 时，显然不需要扔鸡蛋；当鸡蛋数K为 1 时，显然只能线性扫描所有楼层
        if (k==1) return n;
        if (n==0) return 0;
        String key=k+"="+n;
        if (memo887.containsKey(key)){
            return memo887.get(key);
        }
        int res=Integer.MAX_VALUE;
        //二分查找优化线性搜索
        int l=1,r=n;
        while (l<=r){
            int mid=(l+r)/2;
            int subBroken=dp887(k-1,mid-1);
            int subNotBroken=dp887(k,n-mid);
            if (subBroken>subNotBroken){
                r=mid-1;
                res=Math.min(res,subBroken+1);
            }else {
                l=mid+1;
                res=Math.min(res,subNotBroken+1);
            }
        }
        memo887.put(key,res);
        return res;
    }
    public int superEggDrop2(int k, int n) {
        memo887=new HashMap<>();
        return dp887(k,n);
    }

    /*方法3：重新定义dp（状态转移）的含义
    *dp(k,m)数组的定义，确定当前的鸡蛋个数k和最多允许的扔鸡蛋次数m，就知道能够确定F的最高楼层数等于dp(k,m)=n。
    * 当前有 k 个鸡蛋，可以尝试扔 m 次鸡蛋。这个状态下，最坏情况下最多能确切测试一栋 n 层的楼
    * 1、无论你在哪层楼扔鸡蛋，鸡蛋只可能摔碎或者没摔碎，碎了的话就测楼下，没碎的话就测楼上。
    * 2、无论你上楼还是下楼，总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1（当前这层楼）。
    * dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1
    * dp[k][m - 1]就是楼上的楼层数，因为鸡蛋个数k不变，也就是鸡蛋没碎，扔鸡蛋次数m减一；
    * dp[k - 1][m - 1]就是楼下的楼层数，因为鸡蛋个数k减一，也就是鸡蛋碎了，同时扔鸡蛋次数m减一。
    * */
    public int superEggDrop(int k, int n){
        // m 最多不会超过 N 次（线性扫描）
        int[][] dp=new int[k+1][n+1];
        int m=0;
        while (dp[k][m]<n){
            m++;
            for (int i = 1; i <=k ; i++) {
                dp[i][m]=dp[i][m-1]+dp[i-1][m-1]+1;
            }
        }
        return m;
    }




    /*===========================================================================================================================
     *DP 312. 戳气球
     * 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
     * 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。i戳破后i-1和i+1就相邻了
     * 如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。求所能获得硬币的最大数量。
     *dp[i][j] = x表示，戳破气球i和气球j之间（开区间，不包括i和j）的所有气球，可以获得的最高分数为x。dp[i][j] = dp[i][k] + dp[k][j] + points[i]*points[k]*points[j]
     *  */
    public int maxCoins(int[] nums) {
        int n=nums.length;
        int[] points=new int[n+2];
        //将nums前后各加一个数字为1的气球
        points[0]=points[n+1]=1;
        for (int i = 1; i <n+1 ; i++) {
            points[i]=nums[i-1];
        }

        int[][] dp=new int[n+2][n+2];
        // 开始状态转移
        // i 应该从下往上
        for (int i = n; i >=0 ; i--) {
            // j 应该从左往右
            for (int j = i+1; j < n+2; j++) {
                //遍历k作为ij之间最后一个被戳破的气球
                for (int k = i+1; k < j; k++) {
                    dp[i][j]=Math.max(dp[i][j],dp[i][k]+dp[k][j]+points[i]*points[k]*points[j]);
                }
            }
        }
        return dp[0][n+1];
    }





    /*===========================================================================================================================
     *DP 877. 石子游戏
     * 原问题：偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。---先手永远获胜
     * 一般问题：你和你的朋友面前有一排石头堆，用一个数组 piles 表示，piles[i] 表示第 i 堆石子有多少个。你们轮流拿石头，一次拿一堆，但是只能拿走最左边或者最右边的石头堆。
     *          所有石头被拿完后，谁拥有的石头多，谁获胜。石头的堆数可以是任意正整数，石头的总数也可以是任意正整数，这样就能打破先手必胜的局面了。
     *          请你设计一个算法，返回先手和后手的最后得分（石头总数）之差。
     *dp（i_j，count[0]） 表示，对于 piles[i...j] 这部分石头堆，先手能获得的最高分数。dp（i_j，count[0]）= max(piles[i] + dp(i+1_j,count[1]), piles[j] + dp(i_j-1,count[1]))  选左或右，然后变成后手了
     *dp（i_j，count[1]）表示，对于 piles[i...j] 这部分石头堆，后手能获得的最高分数。
     * 状态显然有三个：开始的索引 i，结束的索引 j，当前轮到的人。选择有两个：选择最左边的那堆石头，或者选择最右边的那堆石头。
     *  */
    class Pair {
        int fir, sec;
        Pair(int fir, int sec) {
            this.fir = fir;
            this.sec = sec;
        }
    }
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        // 初始化 dp 数组
        Pair[][] dp = new Pair[n][n];
        for (int i = 0; i < n; i++)
            for (int j = i; j < n; j++)
                dp[i][j] = new Pair(0, 0);
        // 填入 base case
        for (int i = 0; i < n; i++) {
            dp[i][i].fir = piles[i];
            dp[i][i].sec = 0;
        }
        // 斜着遍历数组
        for (int l = 2; l <= n; l++) {
            for (int i = 0; i <= n - l; i++) {
                int j = l + i - 1;
                // 先手选择最左边或最右边的分数
                int left = piles[i] + dp[i+1][j].sec;
                int right = piles[j] + dp[i][j-1].sec;
                // 套用状态转移方程
                if (left > right) {
                    dp[i][j].fir = left;
                    dp[i][j].sec = dp[i+1][j].fir;
                } else {
                    dp[i][j].fir = right;
                    dp[i][j].sec = dp[i][j-1].fir;
                }
            }
        }
        Pair res = dp[0][n-1];
        return res.fir - res.sec> 0;
    }



    /*===========================================================================================================================
     *DP 四键盘问题
     * 有一个特殊的键盘包含以下按键：key1（A）：在屏幕上打印一个'A'。key2（Ctrl-A）：选中整个屏幕。key3（Ctrl-C）：复制选中区域到缓存区。key4（Ctrl-V）：将缓冲区内容输出到上次输入结束位置
     * 现在你可以按n次按键，屏幕最多可以显示几个A
     */
    /* 1. 定义三个状态：第一个状态是剩余的按键次数，用 n 表示；第二个状态是当前屏幕上字符 A 的数量，用 a_num 表示；第三个状态是剪切板中字符 A 的数量，用 copy 表示。
     * dp[n][a_num][copy] 表示在剩余n次按键，当前已经有了a_num个A且剪切板种有copy个A时的最多可显示的A的个数
     * 「选择」是很明显的：4 种，就是题目中提到的四个按键，分别是 A、C-A、C-C、C-V（Ctrl 简写为 C）
     * */
    Map<String,Integer> memo4;
    int dp4(int n,int a_num,int copy){
        //没有按键次数了
        if (n<=0) return a_num;
        String key=n+"#"+a_num+"#"+copy;
        if (memo4.containsKey(key)){
            return memo4.get(key);
        }
        int res=Math.max(dp4(n-1,a_num+1,copy),   //key1
                Math.max(dp4(n-1,a_num+copy,copy), //key4
                        dp4(n-2,a_num,a_num)));  //key2+key3
        memo4.put(key,res);
        return res;
    }
    public int maxA1(int n){
        memo4=new HashMap<>();
        return dp4(n,0,0);
    }

    /*2. 最优按键序列一定只有两种情况：要么一直按 A，要么是这么一个形式：A,A,…C-A,C-C,C-V,C-V,…C-V（当 N 比较大时）。
     定义：dp[i] 表示 i 次操作后最多能显示多少个 A
     对于「按 A 键」这种情况，就是状态 i - 1 的屏幕上新增了一个 A 而已  dp[i] = dp[i - 1] + 1;
     如果要按 C-V，还要考虑之前是在哪里 C-A C-C 的。用一个变量 j 作为若干 C-V 的起点。那么 j 之前的 2 个操作就应该是 C-A C-C 了：
    * */
    public int maxA(int n){
        int[] dp=new int[n+1];
        dp[0]=0;
        for (int i = 1; i <= n; i++) {
            dp[i]=dp[i-1]+1;
            for (int j = 2; j < i; j++) {
                // 全选 & 复制 dp[j-2]，连续粘贴 i - j 次
                // 屏幕上共 dp[j - 2] * (i - j + 1) 个 A
                dp[i]=Math.max(dp[i],dp[j-2]*(i-j+1));
            }
        }
        return dp[n];
    }

    /*===========================================================================================================================
     *DP 494. 目标和
     * 如果我们把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数,
     * 可以推出 sum(A) = (target + sum(nums)) / 2，也就是把原问题转化成：nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2
     * ==有一个背包，容量为 sum，现在给你 N 个物品，第 i 个物品的重量为 nums[i - 1]（注意 1 <= i <= N），每个物品只有一个，请问你有几种不同的方法能够恰好装满这个背包
     * dp[i][j] = x 表示若只在 nums 的前 i 个元素中选择，若目标和为 j，则最多有 x 种方法划分子集。
     * v=dp[0][..] = 0   dp[..][0] = 1
     * dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
     *  */
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for (int n:nums) {
            sum+=n;
        }
        if (sum<target||(sum+target)%2==1||-sum>target){
            //当全部为+时都有比target小，则没有结果。当sumA的结果不是整数时，不符合
            return 0;
        }
        return subsets(nums,(sum+target)/2);
    }
    /* 计算 nums 中有几个子集的和为 sum */
    int subsets(int[] nums, int sum) {
        int n=nums.length;
        int[][] dp=new int[n+1][sum+1];
        for (int i = 0; i < n+1; i++) {
            dp[i][0]=1;
        }
        for (int i = 1; i < n+1; i++) {
            for (int j = 0; j < sum+1; j++) {
                if (j-nums[i-1]<0){
                    // 背包的空间不足，只能选择不装物品 i
                    dp[i][j]=dp[i-1][j];
                }else {
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][sum];
    }
    /* 状态压缩---计算 nums 中有几个子集的和为 sum */
    int subsets1(int[] nums, int sum) {
        int n=nums.length;
        int[] dp=new int[sum+1];
        dp[0]=1;
        for (int i = 1; i < n+1; i++) {
            for (int j = sum; j >=0; j--) {
                //j从后向前遍历，保证j-nums[i-1]没有被覆盖
                if (j-nums[i-1]<0){
                    // 背包的空间不足，只能选择不装物品 i
                    dp[j]=dp[j];
                }else {
                    dp[j]=dp[j]+dp[j-nums[i-1]];
                }
            }
        }
        return dp[sum];
    }







    /*===========================================================================================================================
     *爬楼梯
     * 1.递归
     * 2.非递归的dp：dp[i] = dp[i - 1] + dp[i - 2];
     * */
    public int climbStairs(int n) {
        if(n<=1){
            return 1;
        }
        if (n<3)
            return n;
        return climbStairs(n-1)+climbStairs(n-2);
    }
    public int climbStairs1(int n) {
        return clib(n,1,1);
    }
    public int clib(int n,int a,int b){
        if (n<=1)
            return b;
        return clib(n-1,b,a+b);
    }

    public int climbStairs2(int n) {
        if(n<=1)
            return 1;
        int[] dp=new int[n+1];
        dp[1]=1;
        dp[2]=2;
        for (int i = 3; i <= n; i++) {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }


    /*=================================================================================================================================================================
     *买卖股票问题：
     *188题是最泛化的形式。其他的问题都是这个形式的简化，121是只进行一次交易，相当于 `k = 1`；122是不限交易次数，相当于 `k = +infinity`（正无穷）；
     * 123是只进行 2 次交易，相当于 `k = 2`；188和714也是不限次数，但是加了交易「冷冻期」和「手续费」的额外条件
     *
     * `dp[i][k][0 or 1],0 <= i <= n-1, 1 <= k <= K`:n 为天数，大 K 为最多交易数,0或1表示是否持有
     * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
     * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
     * */

    /*
     *121：买卖股票的最佳时机
     * 1.最大子数组的和:dp[i]表示以第i个差值为结尾的最大子数组的和
     * */
    public int maxProfit1(int[] prices) {
        int n=prices.length;
        if (n<2)
            return 0;
        int[] pro=new int[n-1];
        for (int i = 0; i <n-1; i++) {
            pro[i]=prices[i+1]-prices[i];
        }
        int[] dp=new int[n-1];
        dp[0]=pro[0];
        int res=Math.max(0,dp[0]);
        for (int i = 1; i < n-1; i++) {
            dp[i]=Math.max(dp[i-1]+pro[i],pro[i]);
            res=Math.max(res,dp[i]);
        }
        return res;
    }
    //2.套用,k=1不变，dp变成二维的 dp[i][0](第i天不持有股票的最大利益) = max(dp[i-1][0], dp[i-1][1] + prices[i])
    //dp[i][1](第i天持有股票的最大利益) = max(dp[i-1][1], -prices[i]（前一天不持有股票，在第i天买入，之前没有累计的利益）)
    public int maxProfit11(int[] prices) {
        int n=prices.length;
        int[][] dp=new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i-1==-1){
                dp[i][0]=0;
                dp[i][1]=-prices[i];
                continue;
            }
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
        }
        return dp[n-1][0];
    }

    /*
     *122. 买卖股票的最佳时机 II   k = +infinity
     * 你可以尽可能地完成更多的交易（多次买卖一支股票）。你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     * */
    //计算每一天的差值，将正的差值加起来就是结果
    public int maxProfit2(int[] prices) {
        int n=prices.length;
        int res=0;
        for (int i = 1; i <n; i++) {
            int pro=prices[i]-prices[i-1];
            if (pro>0){
                res+=pro;
            }
        }
        return res;
    }
    //套用：k=+infinity不变，dp变成二维的。
    // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])，dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
    public int maxProfit22(int[] prices) {
        int n=prices.length;
        int[][] dp=new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i-1==-1){
                dp[i][0]=0;
                dp[i][1]=-prices[i];
                continue;
            }
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
    }


    /*
     *123. 买卖股票的最佳时机 III  k = 2
     * 你最多可以完成 两笔 交易。你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     * */
    public int maxProfit3(int[] prices) {
        int n=prices.length;
        int[][][] dp=new int[n][3][2];
        dp[0][2][0]=dp[0][1][0]=0;
        dp[0][2][1]=dp[0][1][1]=-prices[0];
        for (int i = 1; i < n; i++) {
            for (int k = 2; k >=1 ; k--) {
                dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
                dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);
            }
        }
        return dp[n-1][2][0];
    }

    /*
    * 188. 买卖股票的最佳时机 IV
    * 你最多可以完成 k 笔交易。一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。
    * */
    public int maxProfit4(int k, int[] prices) {
        int n=prices.length;
        if (k>n/2)
            return maxProfit2(prices);
        int[][][] dp=new int[n][k+1][2];
        for (int i = 0; i < n; i++) {
            for (int j = k; j >=1 ; j--) {
                if (i-1==-1){
                    dp[0][j][0]=0;
                    dp[0][j][1]=-prices[0];
                    continue;
                }
                dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
                dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
            }
        }
        return dp[n-1][k][0];
    }



    /*
     * 714. 买卖股票的最佳时机含手续费   k = +infinity with fee
     * 整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
     * 每次交易要支付手续费，只要把手续费从利润中减去即可
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)
     * */
    public int maxProfit5(int[] prices, int fee)  {
        int n=prices.length;
        int[][] dp=new int[n][2];
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
    }


    /*
     * 309. 最佳买卖股票时机含冷冻期  第三题，k = +infinity with cooldown
     * 你可以尽可能地完成更多的交易（多次买卖一支股票）:卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
     * 第 i 天选择 `buy` 的时候，要从 i-2 的状态转移，而不是 i-1 。
     * */
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int[][] dp=new int[n][2];
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            if (i-2==-1){
                dp[1][1]=Math.max(dp[0][1],-prices[i]);
                continue;
            }
            dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-prices[i]);
        }
        return dp[n-1][0];
    }

    /*==================================================================================================================================================================
     *打家劫舍:
     * 198:你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * 213:这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
     * 337:二叉树
     * */

    /* 198. 打家劫舍
     * dp[i][1]表示第i个要的最大值，dp[i][0]表示第i个不要的最大值
     * dp[i][1]=dp[i-1][0]+nums[i];dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);
     * dp[0][1]=nums[0],dp[0][0]=0
     * */
    public int rob1(int[] nums) {
        int n=nums.length;
        int[][] dp=new int[n][2];
        dp[0][1]=nums[0];dp[0][0]=0;
        for (int i = 1; i < n; i++) {
            dp[i][1]=dp[i-1][0]+nums[i];
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);
        }
        return Math.max(dp[n-1][0],dp[n-1][1]);
    }
    //dp[i] = x 表示从第 i 间房子开始抢劫，最多能抢到的钱为 x
    //dp[i] = max(dp[i + 1], nums[i] + dp[i + 2])  选择抢还是不抢，抢了的话就下一个只能从i+2开始判断
    public int rob11(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n+2];
        for (int i = n-1; i >=0 ; i--) {
            dp[i]=Math.max(dp[i+1],nums[i]+dp[i+2]);
        }
        return dp[0];
    }


     /* 213. 打家劫舍 II
      *这些房子不是一排，而是围成了一个圈。
      * 首尾房间不能同时被抢，那么只可能有三种不同情况：要么都不被抢；要么第一间房子被抢最后一间不抢；要么最后一间房子被抢第一间不抢。
      */
     public int rob2(int[] nums) {
         int n=nums.length;
         if (n==0){
             return 0;
         }
         if (n==1){
             return nums[0];
         }
         if (n==2){
             return Math.max(nums[0],nums[1]);
         }
         return Math.max(robRange(nums,0,n-2),robRange(nums,1,n-1));
     }
    int robRange(int[] nums,int start,int end){
        int[] dp=new int[nums.length];
        dp[start]=nums[start];
        dp[start+1]=Math.max(dp[start],nums[start+1]);
        for (int i=start+2;i<=end;i++){
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[end];
    }


    /* 337. 打家劫舍 III
     * 这个地方的所有房屋的排列类似于一棵二叉树”
     * 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
     * 还是做抢或者不抢的选择，取收益较大的选择。
     */
    Map<TreeNode,Integer> memo337=new HashMap<>();
    public int rob3(TreeNode root) {
        if (root==null) return 0;
        if (memo337.containsKey(root)){
            return memo337.get(root);
        }
        // 抢，然后去下下家
        int rob_it=root.val+(root.left==null?0:rob3(root.left.left)+rob3(root.left.right)) +(root.right==null?0:rob3(root.right.left)+rob3(root.right.right));
        // 不抢，然后去下家
        int not_rob=rob3(root.left)+rob3(root.right);
        int res=Math.max(rob_it,not_rob);
        memo337.put(root,res);
        return res;
    }
    //方法2：定义dp(TreeNode root)返回一个大小为 2 的数组 arr,arr[0] 表示不抢 root 的话，得到的最大钱数,arr[1] 表示抢 root 的话，得到的最大钱数
    int[] dp337(TreeNode root){
        if (root==null) return new int[]{0,0};
        int[] letf=dp337(root.left);
        int[] right=dp337(root.right);
        // 抢，下家就不能抢了
        int rob_it=root.val+letf[0]+right[0];
        // 不抢，下家可抢可不抢，取决于收益大小
        int not_rob=Math.max(letf[0],letf[1])+Math.max(right[0],right[1]);
        return new int[]{not_rob,rob_it};
    }
    public int rob(TreeNode root) {
        int[] res=dp337(root);
        return Math.max(res[0],res[1]);
    }



    /*==================================================================================================================================================================
     * 1312. 让字符串成为回文串的最少插入次数
     * 给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。请你返回让 s 成为回文串的 最少操作次数 。
     * dp[i][j] 的定义如下：对字符串 s[i..j]，最少需要进行 dp[i][j] 次插入才能变成回文串。
     * dp[i][j] = dp[i + 1][j - 1]; s[i] == s[j]（i+1到j-1已经是回文串了，i==j则i到j直接就是回文串，不需要操作）
     * dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1; s[i] ！= s[j] （如果i+1到j是回文串，则将s[i]添加到s[j]后面即可，如果i到j-1是回文串，则将s[j]添加到s[i]前面即可）
     * 当 i == j 时 dp[i][j] = 0
     * */
    public int minInsertions(String s) {
        int n=s.length();
        int[][] dp=new int[n][n];
        //从下往上，从左向右遍历
        for (int i = n-2; i >=0 ; i--) {
            for (int j = i+1; j < n; j++) {
                if (s.charAt(i)==s.charAt(j)){
                    dp[i][j]=dp[i+1][j-1];
                }else {
                    dp[i][j]=Math.min(dp[i+1][j],dp[i][j-1])+1;
                }
            }
        }
        return dp[0][n-1];
    }



    public static void main(String[] args) {
        int[] prices=new int[]{1};
        int[] nums =new int[]{1,2,3,1};
        String s1="horse";
        String s2="ros";
        Solution_6DP object=new Solution_6DP();
//        System.out.println(object.climbStairs(3));
//        System.out.println(object.maxProfit(prices));
//        System.out.println(object.maxSubArray(nums));
//       System.out.println(object.rob(nums));
        System.out.println(object.maxA(7));
    }
}
